|
Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation (i.e. for every possible information set) at every point in time. In the mathematical optimization method of dynamic programming, backward induction is one of the main methods for solving the Bellman equation.〔Jerome Adda and Russell Cooper, "Dynamic Economics: Quantitative Methods and Applications", Section 3.2.1, page 28. MIT Press, 2003.〕〔Mario Miranda and Paul Fackler, "Applied Computational Economics and Finance", Section 7.3.1, page 164. MIT Press, 2002.〕 In game theory, backward induction is a method used to compute subgame perfect equilibria in sequential games.〔Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.〕 The only difference is that optimization involves just one decision maker, who chooses what to do at each point of time, whereas game theory analyzes how the decisions of several players interact. That is, by anticipating what the last player will do in each situation, it is possible to determine what the second-to-last player will do, and so on. In the related fields of automated planning and scheduling and automated theorem proving, the method is called backward search or backward chaining. In chess it is called retrograde analysis. Backward induction has been used to solve games as long as the field of game theory has existed. John von Neumann and Oskar Morgenstern suggested solving zero-sum, two-person games by backward induction in their ''Theory of Games and Economic Behavior'' (1944), the book which established game theory as a field of study.〔John von Neumann and Oskar Morgenstern, "Theory of Games and Economic Behavior", Section 15.3.1. Princeton University Press. (Third edition, 1953. ) (First edition, 1944.)〕〔(Mathematics of Chess ), webpage by John MacQuarrie.〕 ==An example of decision-making by backward induction== Consider an unemployed person who will be able to work for ten more years ''t'' = 1,2,...,10. Suppose that each year in which he remains unemployed, he may be offered a 'good' job that pays $100, or a 'bad' job that pays $44, with equal probability (50/50). Once he accepts a job, he will remain in that job for the rest of the ten years. (Assume for simplicity that he cares only about his monetary earnings, and that he values earnings at different times equally, i.e., the discount rate is zero.) Should this person accept bad jobs? To answer this question, we can reason backwards from time ''t'' = 10. *At time 10, the value of accepting a good job is $100; the value of accepting a bad job is $44; the value of rejecting the job that is available is zero. Therefore, if he is still unemployed in the last period, he should accept whatever job he is offered at that time. *At time 9, the value of accepting a good job is $200 (because that job will last for two years); the value of accepting a bad job is 2 *$44 = $88. The value of rejecting a job offer is $0 now, plus the value of waiting for the next job offer, which will either be $44 with 50% probability or $100 with 50% probability, for an average ('expected') value of 0.5 *($100+$44) = $72. Therefore, regardless of whether the job available at time 9 is good or bad, it is better to accept that offer than wait for a better one. *At time 8, the value of accepting a good job is $300 (it will last for three years); the value of accepting a bad job is 3 *$44 = $132. The value of rejecting a job offer is $0 now, plus the value of waiting for a job offer at time 9. Since we have already concluded that offers at time 9 should be accepted, the expected value of waiting for a job offer at time 9 is 0.5 *($200+$88) = $144. Therefore, at time 8, it is more valuable to wait for the next offer than to accept a bad job. It can be verified by continuing to work backwards that bad offers should only be accepted if one is still unemployed at times 9 or 10; they should be rejected at all times up to ''t'' = 8. The intuition is that if one expects to work in a job for a long time, this makes it more valuable to be picky about what job to accept. A dynamic optimization problem of this kind is called an optimal stopping problem, because the issue at hand is when to stop waiting for a better offer. Search theory is the field of microeconomics that applies problems of this type to contexts like shopping, job search, and marriage. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「backward induction」の詳細全文を読む スポンサード リンク
|